package algorithm.tree.bst;


import org.junit.Test;

import java.util.LinkedList;

public class TreeSearch {

  @Test
  //二叉树获取查询路径
  public void test1() {
    /**
     *     1
     *  2     3
     * 4 5    7 8
     *    9
     */
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    root.left.right.right = new TreeNode(9);

    root.right = new TreeNode(3);
    root.right.left = new TreeNode(7);
    root.right.right = new TreeNode(8);

    lujing(root, 9);
    System.out.println(list);
    for (TreeNode o : list) {
      System.out.println(o.val);
    }

  }


  static LinkedList<TreeNode> list = new LinkedList();

  /**
   * 二叉树的查询路径， 对于平衡二叉树 和 二叉树都是通用的
   *
   * @param node
   * @param target
   * @return
   */
  public boolean lujing(TreeNode node, int target) {

    if (node == null) return false;
    list.addLast(node);

    if (node.val == target) return true;
    //这个find 很重要，如果在当前节点下查询不到，需要通过这个标识 把节点从队列中移除
    boolean find = false;
    if (node.left != null) {
      find = lujing(node.left, target);
    }
    if (node.right != null) {
      find = lujing(node.right, target);
    }

    if (!find) list.removeLast();
    return find;
  }

  @Test
  public void test2() {
    /**
     *     1
     *  2     3
     * 4 5    7 8
     *    9
     */
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    root.left.right.right = new TreeNode(9);

    root.right = new TreeNode(3);
    root.right.left = new TreeNode(7);
    root.right.right = new TreeNode(8);

    //测试是不是中序遍历
    bsttreeCheck(root);
    System.out.println(order);
    for (int o : order) {
      System.out.println(o);
    }
  }

  LinkedList<Integer> order = new LinkedList<>();

  public void bsttreeCheck(TreeNode treeNode) {
    //判断一个树是不是 搜索二叉树
    if (treeNode == null) return;

    if (treeNode.left != null) {
      bsttreeCheck(treeNode.left);
    }

    order.add(treeNode.val);

    if (treeNode.right != null) {
      bsttreeCheck(treeNode.right);
    }

  }


}
